package com.lmf.recursion;

/**
 * 八皇后问题：递归回溯算法实现，只能计算八皇后问题，总共有多少种摆法
 */
public class Queen {
    //max：表示有多少个皇后
    int max = 8;
    //创建一个一维数组，模拟棋盘；
    //数组下标：表示棋盘行数   数组的值：表示棋盘列数
    int[] arr = new int[max];
    //统计总共有多少种摆法
    static int count;
    //统计总共进行了多少次判断
    static int nums;

    public static void main(String[] args){
        // 测试一把
        Queen queen = new Queen();
        queen.check(0); // 必须是0
        System.out.println("总共多少种摆法："+count);
        System.out.println("总共进行了多少次判断："+nums);
    }

    // 编写一个方法, 放置第n个皇后
    // 注意  进入check时 都会有一个for循环,因此会有回溯
    public void check(int n){
        //n:表示已经摆放皇后的个数
        //当摆放了有最大个数的皇后时，停止摆放皇后
        if (n == max) {//n==8
            print();
            return;
        }
        //从第一行第一列开始摆放皇后，依次摆放，并判断是否冲突
        for (int i = 0; i < arr.length; i++) {
            arr[n] = i;
            //判断当前皇后的位置是否与之前的皇后位置冲突
            if (verify(n)) {
                //若不冲突，则调用递归方法，进行依次摆放皇后位置
                check(n+1);
            }
        }
    }

    //判断每次摆放皇后时，是否与之前的皇后有冲突的方法
    public boolean verify(int n){
        //遍历之前已经摆放的所有皇后
        for (int i = 0; i < n; i++) {
            nums++;
            //1）判断两个皇后是否在同一列：arr[n] == arr[i]
            //2）判断两个皇后是否在同以斜线：Math.abs(n-i) == Math.abs(arr[n] - arr[i])
            //3）判断两个皇后是否在同一行：因为本人使用的一维数组解决方法，因此两个数不可能在同一行。
            if (arr[n] == arr[i] || Math.abs(n-i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    //打印各种摆法数组
    public void print(){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        count++;    //统计总共有多少种摆法
        System.out.println();//数组打印完，换行
    }
}
